package 牛客.二分查找_排序;

public class BM20数组中的逆序对 {
    public int reversePairs(int[] nums) {
        //分治，利用归并排序的思想统计逆序对
        if (nums.length<2) {
            return 0;
        }
        //辅助数组，用来归并
        int[] helper=new int[nums.length];
        return process(nums,0,nums.length-1,helper);
    }

    private int process(int[] nums, int left, int right, int[] helper) {
        if (left==right) {
            return 0;
        }
        int mid=(right-left)/2+left;
        int leftPairs=process(nums,left,mid,helper);
        int rightPairs=process(nums,mid+1,right,helper);

        int crossPairs=merge(nums,left,mid,right,helper);
        return leftPairs+rightPairs+crossPairs;
    }

    private int merge(int[] nums, int left, int mid, int right, int[] helper) {
        for (int i = left; i <=right ; i++) {
            helper[i]=nums[i];
        }

        int res=0;
        int i=left;
        int j=mid+1;
        for (int k = left; k <=right ; k++) {
            //先得判断边界情况！
            if (i==mid+1) {
                //左区间排好，右区间剩余
                nums[k]=helper[j];
                j++;
            }else if (j==right+1) {
                nums[k]=helper[i];
                i++;
            }else if (helper[i]>helper[j]) {
                nums[k]=helper[j];
                res += (mid-i+1);//统计逆序对的数量
                j++;
            }else {
                nums[k]=helper[i];
                i++;
            }
        }
        return res;
    }

    public int InversePairs1(int [] array) {
        //暴力，超时
        int res=0;
        for (int i = 0; i <array.length; i++) {
            int tmp=array[i];
            for (int j = i+1; j <array.length ; j++) {
                if (tmp>array[j]) {
                    res++;
                }
            }
        }
        return res;
    }
}
